package cn.edu.njust.alg.leetcode;

public class Leetcode_67_AddBinary {

	/*
	 * Given two binary strings, return their sum (also a binary string).
	 * 
	 * For example, a = "11" b = "1" Return "100".
	 */
	public String addBinary(String a, String b) {
		StringBuffer bf = new StringBuffer();
		int c = 0;

		int i = a.length() - 1, j = b.length() - 1;
		for (; i >= 0 && j >= 0; i--, j--) {
			int ac = a.charAt(i) - '0';
			int bc = b.charAt(j) - '0';
			int n = (ac + bc + c) % 2;
			bf.append((char) (n + '0'));
			c = (ac + bc + c) / 2;
		}
		while (i >= 0) {
			int ac = a.charAt(i) - '0';
			int n = (ac + c) % 2;
			bf.append((char) (n + '0'));
			c = (ac + c) / 2;
			i--;
		}
		while (j >= 0) {
			int bc = b.charAt(j) - '0';
			int n = (bc + c) % 2;
			bf.append((char) (n + '0'));
			c = (bc + c) / 2;
			j--;
		}
		if (c > 0) {
			bf.append((char) (c + '0'));
		}

		return bf.reverse().toString();
	}

	public static void main(String[] args) {
		String a = "11";
		String b = "1";

		System.out.println(new Leetcode_67_AddBinary().addBinary(a, b));
	}

}
